class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = nums.size();
        int res = 0;
        std::vector<int> dp(nums.size(), 1);
        for(int i = 0; i < len; i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(nums[i] > nums[j])
                {
                    dp[i] = std::max(dp[j]+1, dp[i]);
                }
            }
        }

        for(int i = 0; i < len; i++)
            res = res > dp[i] ? res : dp[i];

        return res;
    }
};

// o(nlogn)
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        std::vector<int> res;
        res.push_back(nums[0]);
        for(int i = 1; i < nums.size(); i++)
        {
            int left = 0;
            int right = res.size()-1;
            if(nums[i] > res[right])
            {
                res.push_back(nums[i]);
                continue;
            }
            while(left <= right)
            {
                int mid = (left+right) / 2;
                if(res[mid] >= nums[i])
                {
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            res[left] = nums[i];
        }

        return res.size();
    }
};